// 每个主件算一类，其下有两个附件，可以考虑选几个和不选
// 相当于是一个分组背包问题
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 32010, M = 65;
int n, m;
int f[N];
PII master[M];
vector<PII> servent[M];

int main()
{
    cin >> m >> n;
    for (int i = 1; i <= n; ++i)
    {
        int v, p, q;
        cin >> v >> p >> q;
        p *= v;
        if (!q)
            master[i] = {v, p};
        else
            servent[q].push_back({v, p});
    }
    // 接下来开始分组背包问题
    for (int i = 1; i <= n; ++i)
        for (int u = m; u >= master[i].first; --u)
        {
            // 枚举所有可能的情况，利用位表示当前物品是否被选择
            for (int j = 0; j < 1 << servent[i].size(); ++j)
            {
                int v = master[i].first, w = master[i].second;
                for (int k = 0; k < servent[i].size(); ++k)
                    if ((j >> k) & 1)
                    {
                        v += servent[i][k].first;
                        w += servent[i][k].second;
                    }
                if (u >= v)
                    f[u] = max(f[u], f[u - v] + w);
            }
        }
    cout << f[m] << endl;
    return 0;
}
